﻿/*THÔNG TIN*********************************************************************
 *Tập tin		: Traverse.h
 *Mô tả			: Thư viện các thuật toán duyệt đồ thị
 *Ngày tạo		: 29/08/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

/*Lớp các thuật toán duyệt đồ thị*/
class TRAVERSE	: public GRAPH{
private:
	// Mảng lưu các nhóm đỉnh liên thông
	vector <uint16_t> group;
	// Số vùng liên thông
	uint16_t group_count;

public:
	// Phương thức khởi tạo
	TRAVERSE();

	// Khởi tạo cho thuật toán duyệt
	void Initiate_traverse();
	// Duyệt theo chiều rộng
	void BFS(uint16_t start);
	// Duyệt theo chiều sâu
	void DFS(uint16_t ver);
	// In kết quả duyệt ra file
	void Print_result_to_out(string input_file, string opt);
	// In đồ thị với thứ tự duyệt các đỉnh
	void Print_result_to_dot(string input_file, string opt);

	// Khởi tạo cho thuật toán tìm số thành phần liên thông
	void Initiate_count(bool mode, string input_file);
	// Duyệt theo chiều sâu để đếm số thành phần liên thông
	void BFS_to_count(uint16_t start);
	// Tìm các thành phần liên thông
	void Find_connected_component();
	// In kết quả tìm kiếm thành phần liên thông
	void Print_connected_components_to_out(string input_file);
};/*Kết thúc khai báo lớp TRAVERSE*/

/*Phương thức khởi tạo*/
TRAVERSE :: TRAVERSE()	{
	group_count = 0;
	group.clear();
}/*Kết thúc phương thức TRAVERSE*/

/*Khởi tạo cho thuật toán duyệt*/
void TRAVERSE :: Initiate_traverse()	{
	final.resize( Get_vertices() );
	result.clear();

	cout << "Thuc hien thuat toan duyet..........";
	start_time = clock();
}/*Kết thúc phương thức Initiate_traverse*/

/*Thuật toán duyệt đồ thị theo chiều rộng*/
void TRAVERSE :: BFS(uint16_t start)	{
	// Khởi tạo
	vector <uint16_t> queue ( Get_vertices(), UINT16_MAX);
	queue[0] = start;
	final[start] = true;
	uint16_t i, left = 0, right = 0;

	while (left <= right)	{
		i = queue[ left++ ];
		result.push_back(i);

		for (uint16_t j=0; j!=Get_vertices(); ++j)
			if ( Get_length(i, j)!=UINT16_MAX && !final[j] )	{
				queue[ ++right ] = j;
				final[j] = true;
			}
	}
}/*Kết thúc phương thức BFS*/

/*Thuật toán duyệt đồ thị theo chiều sâu*/
void TRAVERSE :: DFS(uint16_t ver)	{
	final[ver] = true;
	result.push_back(ver);

	for (uint16_t i=0; i!=Get_vertices(); ++i)
		if (Get_length(ver, i)!=UINT16_MAX && !final[i])
			DFS(i);
}/*Kết thúc phương thức DFS*/

/*In kết quả ra file*/
void TRAVERSE :: Print_result_to_out(string input_file, string opt)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, opt, ".out");

	// Bắt đầu lưu file
	f << "Thu tu duyet cac dinh la: \n";

	for (uint16_t i=0; i!=result.size(); ++i)
		f << result[i]+1 << " ";

	f << "\n";

	cout << "Xong.\n";
	f.close();
}/*Kết thúc phương thức Print_result*/

/*In đồ thị với thứ tự duyệt các đỉnh*/
void TRAVERSE :: Print_result_to_dot(string input_file, string opt)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, opt, ".dot");

	// Bắt đầu lưu file
	f << "digraph " << input_header << opt << " {\n";

	for (uint16_t i=0; i!=Get_vertices(); ++i)
		for (uint16_t j=0; j!=Get_vertices(); ++j)	{
			if (Get_length(i, j) > 0.0 && Get_length(i, j) < UINT16_MAX)	{
				f << i+1;

				for (uint16_t k = 0; k!=result.size(); ++k)
					if (result[k] == i)	{
						f << "." << k+1;
						break;
					}

				f << " -> " << j+1;

				for (uint16_t k = 0; k!=result.size(); ++k)
					if (result[k] == j)	{
						f << "." << k+1;
						break;
					}

				f << " [label = \"" << Get_length(i, j) << "\"]\n";
			}
		}

	string alg(opt.begin()+1, opt.end());
	f << "label = \"\\n\\nThu tu duyet do thi theo thuat toan "
	  << alg << "\\nvoi du lieu tu file " << input_file << "\"\n}";

	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_result_to_dot*/

/*Khởi tạo cho thuật toán tìm số thành phần liên thông*/
void TRAVERSE :: Initiate_count(bool mode, string input_file)	{
	group.resize( Get_vertices() );

	cout << "Thuc hien thuat toan tim so vung lien thong..........";
	start_time = clock();
}/*Kết thúc phương thức Initiate_count*/

/*Duyệt theo chiều sâu để đếm số thành phần liên thông*/
void TRAVERSE :: BFS_to_count(uint16_t start)	{
	uint16_t i, left = 0, right = 0;
	vector <uint16_t> queue ( Get_vertices(), UINT16_MAX);
	queue[0] = start;

	while (left <= right)	{
		i = queue[ left++ ];

		for (uint16_t j=0; j!=Get_vertices(); ++j)
			if ( Get_length(i, j)!=UINT16_MAX && group[j]==0 )	{
				queue[ ++right ] = j;
				group[j] = group[i];
			}
	}
}/*Kết thúc phương thức BFS_to_count*/

/*Tìm các thành phần liên thông*/
void TRAVERSE :: Find_connected_component()	{
	for (uint16_t i=0; i!=Get_vertices(); ++i)
		if (group[i] == 0)	{
			group[i] = (++group_count);
			BFS_to_count(i);
		}
}/*Kết thúc phương thức Find_connected_component*/

/*In kết quả tìm vùng liên thông ra file*/
void TRAVERSE :: Print_connected_components_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Connect", ".out");

	// Bắt đầu lưu kết quả
	if (group_count == 1)
		f << "Do thi da cho lien thong.\n";
	else	{
		f << "Co " << group_count << " thanh phan lien thong";

		for (uint16_t i=1; i<=group_count; ++i)	{
			f << "\nThanh phan " << i << " gom cac dinh: ";

			for (uint32_t j=0; j!=group.size(); ++j)
				if (group[j] == i)
					f << j << " ";
		}
	}

	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_connected_components_to_out*/
